1. Field of the Invention
The present invention relates to a method and system for reducing program execution time. More particularly, the present invention relates to a method and system for reducing program execution time in a multiprocessor system.
2. Description of Related Art
Multiprocessor systems, e.g. computing systems which include multiple processors, are widely used in fields such as scientific computation and simulation. In such systems, an application program generates multiple processes and assigns the processes to individual processors. The processors each perform their processing while communicating with each other by using, for example, a shared memory space.
Simulation systems use software for simulation in mechatronics systems for robots, vehicles, and airplanes. The development of electronic component and software technology has enabled electronic control of machines such as robots, vehicles, or airplanes using a wireless LAN or wired connections spread over the machine.
Although machines are fundamentally mechanical devices, they depend on software systems. Accordingly, in product development, a great amount of time, huge cost, and many people are required for the development of control programs and tests for the programs.
Hardware in the loop simulation (HILS) is a technique that has been conventionally used for such tests. In particular, an environment for testing the electronic control units (ECUs) of an entire vehicle is called full-vehicle HILS. In full-vehicle HILS, actual ECUs are connected to a hardware device for emulating an engine mechanism or a transmission mechanism, for example, in a laboratory. Tests are then carried out for predetermined scenarios. Outputs from the ECUs are inputted to a monitoring computer, and are then displayed. Thus, the test operator checks for abnormal operation while looking at the display.
However, in HILS, a special hardware device is required and physical wiring must be made between the special hardware device and actual ECUs. Thus, HILS involves much advance preparation. In addition, when a test is to be performed by replacing ECUs with different ones, the wiring needs to be physically rearranged. This requires time and effort. Moreover, since actual ECUs are used, real-time testing is needed. Accordingly, when a test is performed for many scenarios, a large amount of time is required. Furthermore, hardware devices for HILS emulation are generally extremely expensive.
To address the disadvantages of HILS, a technique using software without using any expensive emulation hardware device, called software in the loop simulation (SILS), has been proposed. In SILS, systems such as microcomputers, input/output circuits, control scenarios, engines, and transmissions, are all emulated by a software simulator. By use of this technique, a test can be carried out without using actual ECU hardware.
An example of a system for supporting SILS is MATLAB™/Simulink™, which is a simulation modeling system available from Cybernet Systems Co., LTD. By using MATLAB™/Simulink™, a simulation program can be created by arranging functional blocks A, B, C, . . . J on a display through a graphical interface, and then specifying process flows as shown by arrows in FIG. 1.
When a block diagram including the functional blocks A, B, C, . . . J is created by MATLAB™/Simulink™, each function can be converted into a C source code describing an equivalent function by a function of Real-Time Workshop™. By compiling the C source code, a simulation can be performed as a SILS in a different computer system.
In particular, a computer system is a multiprocessor system can contribute much to an improvement of processing speed by dividing processing into as many processes as possible and assigning the divided process blocks to individual processors.
Conventional critical path (CP) scheduling techniques are known. By using a CP scheduling technique, the block diagram shown in FIG. 1 is converted into a task graph shown in FIG. 2. The task graph shown in FIG. 2 consists of four vertical rows in which the process lines are assigned to four individual CPUs operating in parallel. With this configuration, the processing speed can be twice as fast as that of the case in which the processing is executed by a single CPU. However, the critical path in FIG. 2 is a path consisting of B-D-F-H-J. The processing time cannot be reduced to be shorter than the time required for the CPU to process this critical path.
Japanese Unexamined Patent Application Publication No. Hei 6-83608 (JP-06083608-A2) discloses a technique for detecting, by a critical path analysis, a bottleneck for program execution by a parallel computer.
Japanese Unexamined Patent Application Publication No. Hei 7-21240 (JP-07021240-A2) relates to layout design for a logical circuit, and discloses a system for shortening the critical path and minimizing the number of nets crossing a cut line.
The above system includes: a critical path extraction unit for extracting a critical path; a cut line generation unit for generating a cut line; a merge pair selection unit for determining a block to be merged with each block on the basis of the connection degrees of the blocks and critical path information; a merging unit for merging each block with the block determined by the merge pair selection unit; and a pair-wise unit for changing pairs so that the number of nets crossing the cut line is minimized.
Japanese Patent Application Publication Hei 8-180100 (JP-08180100-A2) discloses a technique for calculating an optimal solution at a high speed for a job shop scheduling problem including machine assignment. In this technique, an efficient neighborhood is generated and is then combined with an approximate solution.
Japanese Unexamined Patent Application Publication Hei 6-83608 and Japanese Patent Application Publication Hei 8-180100 each disclose only an overview of task scheduling.
In addition, Japanese Unexamined Patent Application Publication Hei 7-21240 describes a technique for shortening the critical path in the layout design of a logical circuit, but the critical path in question is one in a physical layout. Accordingly, the technique is not applicable to logical critical path processing by software.